/**
*  @file Locate.c
 *  @desc 实现一个带访问频率统计功能的双向循环链表，支持节点按访问频率自动排序。
 *        包括节点插入（头插、尾插）、访问定位（locate）并重排、链表打印等功能。
 *  @author WangBlue (wangjiping596@gmail.com)
 *  @date 2025-08-04 11:02
 *  @version 1.0
 */


#include <stdio.h>
#include <stdlib.h>

// ====================== 节点结构定义 ======================

/**
 * @struct node
 * @brief 双向链表节点结构，包含访问频率字段
 *
 * - data：节点数据
 * - freq：该节点被 locate 操作访问的次数（初始化为 1）
 * - next：后继指针
 * - pre：前驱指针
 */
typedef struct node {
	int data;
	int freq;
	struct node *next;
	struct node *pre;
} node, *link;

// ====================== 基础操作函数 ======================

/**
 * @brief 创建一个带初始值的节点
 * @param value 节点值
 * @return 返回节点指针，若内存分配失败返回 NULL
 */
link createNode(int value) {
	link newNode = (link) malloc(sizeof(node));
	if (newNode == NULL) return NULL;
	newNode->data = value;
	newNode->next = NULL;
	newNode->pre  = NULL;
	newNode->freq = 1;  // 初始访问频率设为 1
	return newNode;
}

/**
 * @brief 初始化双向循环链表头节点
 * @param head 链表头节点地址
 */
void initNode(link *head) {
	link newNode = createNode(0);  // 头节点不存储有效数据
	if (newNode == NULL) return;
	*head = newNode;

	(*head)->next = *head;  // 自环
	(*head)->pre = *head;
}

/**
 * @brief 打印链表中所有节点的值和访问频率（跳过头节点）
 * @param head 头节点
 */
void printList(link head) {
	if (head == NULL || head->next == head) return;
	link cur = head->next;
	while (cur != head) {
		printf("value is %d, freq is %d\n", cur->data, cur->freq);
		cur = cur->next;
	}
	printf("\n");
}

// ====================== 插入函数 ======================

/**
 * @brief 在链表头部插入节点（头插法）
 * @param head 头节点
 * @param value 插入的数据值
 */
void istHead(link head, int value) {
	link newNode = createNode(value);
	if (newNode == NULL) return;

	newNode->next = head->next;
	newNode->pre = head;
	head->next->pre = newNode;
	head->next = newNode;
}

/**
 * @brief 在链表尾部插入节点（尾插法）
 * @param head 头节点
 * @param value 插入的数据值
 */
void istTail(link head, int value) {
	link newNode = createNode(value);
	if (newNode == NULL) return;

	link last = head->pre;
	newNode->next = last->next;  // 等价于 head
	newNode->pre = last;

	last->next = newNode;
	head->pre = newNode;
}

// ====================== 访问并重排节点 ======================

/**
 * @brief locate 函数用于：
 *  - 找到值为 x 的节点
 *  - 增加其访问频率 freq
 *  - 根据 freq 对链表重新排序（按 freq 降序）
 *
 * @param head 头节点
 * @param x 要查找的数据值
 */
void locate(link head, int x) {
	if (head == NULL || head->next == head) return;

	// 1. 遍历链表，找到值为 x 的节点
	link cur = head->next;
	while (cur != head && (cur->data != x)) {
		cur = cur->next;
	}
	if (cur == head) return;  // 未找到目标值

	// 2. 增加频率
	cur->freq++;

	// 3. 取下当前节点
	cur->pre->next = cur->next;
	cur->next->pre = cur->pre;

	// 4. 从头开始，找到第一个频率 <= 当前节点的节点
	link temp = head->next;
	while (temp != head && (temp->freq > cur->freq)) {
		temp = temp->next;
	}

	// 5. 插入到合适位置（在 temp 前）
	link pre;
	if (temp == head) {
		// 频率最大，插入最前面
		pre = NULL;
	} else {
		pre = temp->pre;
	}

	// 6. 插入操作
	if (pre == NULL) {
		// 插入头部
		cur->next = head->next;
		cur->pre = head;
		head->next->pre = cur;
		head->next = cur;
	} else {
		// 插入到 pre 与 pre->next 之间
		cur->next = pre->next;
		cur->pre = pre;
		pre->next->pre = cur;
		pre->next = cur;
	}
}

// ====================== 测试入口 ======================

int main() {
 	link head = NULL;
    initNode(&head);          // 初始化链表

    // 插入初始值（尾插）
    istTail(head, 1);
    istTail(head, 2);
    istTail(head, 3);

    // 多次访问特定节点，触发频率调整和重排
    locate(head, 1);
    locate(head, 3);
    locate(head, 3);
    locate(head, 3);
    locate(head, 2);
    locate(head, 2);
    locate(head, 2);
    locate(head, 2);
    locate(head, 1);
    locate(head, 1);

    // 输出最终链表结构
    printList(head);
}
